//
//  XBDeepFirstSearch.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/22.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBDeepFirstSearch.h"

// --- 代码来自啊哈算法
/*
 深度优先遍历的思想:
 
首先以一个未被访问过的顶点作为其实顶点，沿着当前顶点的边走到未访问过的顶点。当没有未访问过的顶点时候，则回到上一个顶点。继续试探访问别的顶点。
 
 直到所有的顶点都被访问过。
 */
// 深度优先搜索：解决于当下如何做，下一步如何做和当下如何做是一样的

void dfsM(int step)
{
    // 判断边界
    //尝试每一种可能 for()
    {
        //继续下一步 dfs(step+1)
        
    }
    //返回
}

// 深度优先搜索 -- 实现1-n的全排列问题 1<n<=9
static int a[10];
static int book[10];
void dfsC(int cur,int n)
{
    int i,k=0;
    if(cur==n+1)//全部放满的时候就可进行一次输出了
    {
        for (i=1; i<=n; i++) {
            printf("%d",a[i]);
        }
        printf("\n");
        return;
    }
    for (k=1;k<=n; k++) //k是表示的数字，数组a是盒子，book数组是标记数字是否被使用
    {
        if (book[k]==0)  //如果数字k没有被使用，那么就把k放在盒子a[i]的位置，就是当前位置
        {
            a[cur]=k;
            book[k]=1;//并且要对k进行标记，
            dfsC(cur+1,n); //并且继续填充下一个
            book[k]=0;//取消对数字k的标记
        }
    }
}
void testDfs()
{
    dfs(1,3);//表示从第一个位置开始计算
}

// --- 计算最短路径问题

//计算最短路径问题案例

/*
 
 输入：
 5 8
 1 2 2
 1 5 10
 2 3 3
 2 5 7
 3 1 4
 3 4 4
 4 5 5
 5 3 3
 
 第一行的5表示有5个城市，编号1-5，8表示有八条公路，接下来的8行没行是类似于“a b c”这样的数据
 
 表示有一条公路可以从城市a走到城市b，并且距离为c
 
 这里的公路都是单行
 
 a b c仅仅表示有一条路可以从城市a到b，并不表示b也有一条路可以到a，求1号城市到5号城市的最短路径的算法。
 
 
 
 
 已知有5个城市和8条公路，可以用一个5*5的矩阵来保存信息，
 
 */
#define MA 999999999
static int min=MA,n2,e[101][101];//假设999999999为正无穷
//cur是当前城市的编号，dis是已经走过的路程
void dfsWay(int cur,int dis)
{
    int j;
    //如果当前走过的路程大于之前找到的最短路径，没必要接着尝试了
    if (dis>min) {
        return;
    }
    if(cur==n2)//判断是否到达目标城市
    {
        if (dis) {
            min=dis;//更新最小值
        }
    }
    for(j=1;j<=n2;j++)//1号城市到n号城市逐个尝试
    {
        if (e[cur][j]!=MA&&book[j]==0)//判断当前城市cur到城市j是否有路，并且判断j是否已经在走过的路径里面。
        {
            book[j]=1;
            dfsWay(j, dis+e[cur][j]);
            book[j]=0;//之前是试探完毕了，应该清除原来的标记状态
        }
    }
    return;
}
int searchCity()
{
    
    int i,j,m,a,b,c;
    scanf("%d %d",&n2,&m);
    //初始化二维矩阵
    for (i=1; i<=n2; i++)
    {
        for (j=1; j<=n2; j++) {
            if (i==j) {
                e[i][j]=0;
            }else
            {
                e[i][j]=MA;
            }
        }
        
    }
    //读城市之间的道路
    for(i=1;i<=m;i++)
    {
        scanf("%d %d %d",&a,&b,&c);
        e[a][b]=c;
    }
    //从1号城市出发
    book[1]=1;
    dfs(1, 0);
    printf("%d",min);
    return 0;
}








